《剑指offer》 21.调整数组顺序使奇数位于偶数前面

note:数组内凡是需要交换位置的题目,很容易想到双指针的解法,快慢指针、首尾指针都是常见的应用。

题目描述

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

示例:

1
2
3
输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。

提示:

  • 0 <= nums.length <= 50000
  • 1 <= nums[i] <= 10000

方法一 双指针之快慢指针

思路

常见的快慢指针是行进速度(+1、+2)不同,不过这道题目中快慢指针则是指慢指针有时可以停下来。

这道题归根结底就是让双指针分别指向奇书偶数,如果跑得快的指针指向了奇数,跑的慢的指针指向了偶数,则进行交换。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int slow=0,fast = 0;
while(fast<nums.size()){
if(nums[fast]%2==1){
swap(nums[slow],nums[fast]);
slow++;
}
fast++;
}
return nums;
}
};

复杂度分析

  • 时间复杂度$O(n)$。快指针要依次遍历所有的数
  • 空间复杂度$O(1)$。没有使用额外空间

方法二 双指针之首尾指针

思路

同理,用两个指针找应该进行互换的元素。

不同的在于,我们让首指针去找第一个偶数,找到后不动,让尾指针去找第一个奇数,找到后进行交换,重复上述操作,直到首尾指针相遇。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
if (nums[left]%2==1) {
left ++;
continue;
}
if (nums[right]%2==0) {
right --;
continue;
}
swap(nums[left++], nums[right--]);
}
return nums;
}
};

复杂度分析

  • 时间复杂度$O(n)$。同理需要首尾指针遍历完所有的数
  • 空间复杂度$O(1)$。不需要额外的空间。